

#ifndef	_RED_BLACK_TREE_H_
#define	_RED_BLACK_TREE_H_

#include "Basic/Basic.hpp"
#include "RedBlackNode.hpp"

template <typename T> class RedBlackTree{
protected:
	RedBlackNode<T> *root;
	
public:
	CALLCONV RedBlackTree(RedBlackNode<T> *initialNode = (RedBlackNode<T>*)0){
		root = initialNode;
	}

	CALLCONV RedBlackTree(T key){
		root = new RedBlackNode<T>(key);
	}
	
	inline void initialize(RedBlackNode<T> *initialNode = (RedBlackNode<T>*)0){
		root = initialNode;
	}
	
#ifdef	_TEST_RED_BLACK_
	inline dump(void printKey(T)){
		root->dump(printKey);
		std::cout << std::endl;
	}
#endif
	
	inline bool isEmpty(){
		if(this == (RedBlackTree*)0) return true;
		return root == (RedBlackNode<T>*)0;
	}
	inline unsigned getSize(){
		if(this == (RedBlackTree*)0) return 0;
		return root->getSize();
	}
	
	CALLCONV RedBlackNode<T>* getFirstNode(){
		if(this == (RedBlackTree*)0) return (RedBlackNode<T>*)0;
		if(root == (RedBlackNode<T>*)0) return (RedBlackNode<T>*)0;
		RedBlackNode<T> *temp = root;
		while(temp->getLeft() != (RedBlackNode<T>*)0) temp = temp->getLeft();
		return temp;
	}
	CALLCONV RedBlackNode<T>* getLastNode(){
		if(this == (RedBlackTree*)0) return (RedBlackNode<T>*)0;
		if(root == (RedBlackNode<T>*)0) return (RedBlackNode<T>*)0;
		RedBlackNode<T> *temp = root;
		while(temp->getRight() != (RedBlackNode<T>*)0) temp = temp->getRight();
		return temp;
	}
	
	CALLCONV RedBlackNode<T>* findNodeByElement(T element){
		if(this == (RedBlackTree*)0) return (RedBlackNode<T>*)0;
		RedBlackNode<T> *temp = root;
		while(temp != (RedBlackNode<T>*)0){
			if(element == temp->key) return temp;
			if(element < temp->key) temp = temp->getLeft();
			else temp = temp->getRight();
		}
		return (RedBlackNode<T>*)0;
	}
	
	CALLCONV RedBlackNode<T>* findLowestNodeByFloor(T floorElement, bool include){
		if(this == (RedBlackTree*)0) return (RedBlackNode<T>*)0;
		RedBlackNode<T> *result = (RedBlackTree*)0, *temp = root;
		while(temp != (RedBlackTree*)0){
			if(temp->key > floorElement ||
					temp->key == floorElement && include){
				result = temp;
				temp = temp->getLeft();
			}else{
				temp = temp->getRight();
			}
		}
		return result;
	}
	CALLCONV RedBlackNode<T>* findHighestNodeByCeiling(T ceilingElement, bool include){
		if(this == (RedBlackTree*)0) return (RedBlackNode<T>*)0;
		RedBlackNode<T> *result = (RedBlackTree*)0, *temp = root;
		while(temp != (RedBlackTree*)0){
			if(temp->key < ceilingElement ||
					temp->key == ceilingElement && include){
				result = temp;
				temp = temp->getRight();
			}else{
				temp = temp->getLeft();
			}
		}
		return result;
	}
	
	
	CALLCONV bool addNode(RedBlackNode<T> *node){
		if(this == (RedBlackTree*)0) return false;
		if(node == (RedBlackNode<T>*)0) return false;
		if(root == (RedBlackNode<T>*)0){
			root = node;	// case 1
			return true;
		}
		RedBlackNode<T> *temp = root;
		while(true){
			if(node->key >= temp->key){
				if(temp->getRight() != (RedBlackNode<T>*)0){
					temp = temp->getRight();
				}else{
					temp->_addRightLeaf(node);
					node->setRed();
					if(temp->_isRed()){
						typename RedBlackNode<T>::RedBlackPointer rbptr(temp);
						doubleRed(rbptr);
						root = root->getRoot();
					} // else case 2
					break;
				}
			}else{	// node->key < temp->key
				if(temp->getLeft() != (RedBlackNode<T>*)0){
					temp = temp->getLeft();
				}else{
					temp->_addLeftLeaf(node);
					node->setRed();
					if(temp->_isRed()){
						typename RedBlackNode<T>::RedBlackPointer rbptr(temp);
						rbptr.flag.value = 1;
						doubleRed(rbptr);
						root = root->getRoot();
					} // else case 2
					break;
				}
			}
		}
		return true;
	}
	
protected:
	CALLCONV static void doubleRed(typename RedBlackNode<T>::RedBlackPointer rbptr){
		bool goUp, isLeft = (rbptr.flag.value != 0);
		rbptr.flag.value = 0;
		do{
			goUp = false;
			RedBlackNode<T> *parent = rbptr.node->getParent();
			RedBlackNode<T> *sibling;
			if(rbptr.node->isLeft()){
				sibling = parent->getRight();
				if(sibling->isRed()){	// case 3
					rbptr.node->setBlack();
					sibling->setBlack();
					rbptr.node = parent->getParent();
					if(rbptr.node != (RedBlackNode<T>*)0){
						// node's grandparent is not root
						parent->setRed();
						if(rbptr.node->_isRed()){
							isLeft = parent->left.flag.value;
							goUp = true;
						}
					}
				}else{
					if(!isLeft){	// node's right is red (left-right, case 4)
						rbptr.node->rotateLeft();
					}
					// left-left, case 5
					parent->rotateRight();
				}
			}else{	// rbptr.node->isRight()
			// because the node is red, it is not root and must have a parent
				sibling = parent->getLeft();
				if(sibling->isRed()){	// case 3
					rbptr.node->setBlack();
					sibling->setBlack();
					rbptr.node = parent->getParent();
					if(rbptr.node != (RedBlackNode<T>*)0){
						// node's grandparent is not root
						parent->setRed();
						if(rbptr.node->_isRed()){
							isLeft = parent->left.flag.value;
							goUp = true;
						}
					}
				}else{
					if(isLeft){	// node's left is red (right-left, case 4)
						rbptr.node->rotateRight();
					}
					// right-right, case 5
					parent->rotateLeft();
				}
			}
		}while(goUp);
	}
	
	inline void swapKey(RedBlackNode<T> *a, RedBlackNode<T> *b){
		T temp = a->key;
		a->key = b->key;
		b->key = temp;
	}
	
	CALLCONV void swapNode(RedBlackNode<T> *a, RedBlackNode<T> *b){
		typename RedBlackNode<T>::RedBlackPointer  rbptr;
		rbptr = a->left;
		a->left = b->left;
		b->left = rbptr;
		
		rbptr = a->right;
		a->right = b->right;
		b->right = rbptr;
		
		rbptr = a->parent;
		a->parent = b->parent;
		b->parent = rbptr;
		
		RedBlackNode<T> *node = a->getLeft();
		if(node == a) a->_setLeftChild(b);
		else if(node != (RedBlackNode<T>*)0) node->setParent(a);
		
		node = a->getRight();
		if(node == a) a->_setRightChild(b);
		else if(node != (RedBlackNode<T>*)0) node->setParent(a);
		
		node = b->getLeft();
		if(node == b) b->_setLeftChild(a);
		else if(node != (RedBlackNode<T>*)0) node->setParent(b);
		
		node = b->getRight();
		if(node == b) b->_setRightChild(a);
		else if(node != (RedBlackNode<T>*)0) node->setParent(b);
		
		if((node = a->getParent()) != b){
			rbptr.node = a;
			if(a->isLeft()){
				rbptr.flag.value = node->left.flag.value;
				node->left = rbptr;
			}else if(a->isRight()){
				rbptr.flag.value = node->right.flag.value;
				node->right = rbptr;
			}
		}
		
		if((node = b->getParent()) != a){
			rbptr.node = b;
			if(b->isLeft()){
				rbptr.flag.value = node->left.flag.value;
				node->left = rbptr;
			}else if(b->isRight()){
				rbptr.flag.value = node->right.flag.value;
				node->right = rbptr;
			}
		}
	}
	
	CALLCONV static void doubleBlack(typename RedBlackNode<T>::RedBlackPointer rbptr){
		bool goUp, isLeft = (rbptr.flag.value != 0);
		rbptr.flag.value = 0;
		do{
			goUp = false;
			RedBlackNode<T> *sibling;	// sibling of the deleted black node must exist
			if(isLeft){
				sibling = rbptr.node->getRight();
				if(sibling->_isRed()){
					rbptr.node->rotateLeft();	// case 2
				}
				
				sibling = rbptr.node->getRight();	// now it must be a black node
				if(sibling->getRight()->isRed()){	// right-right, case 6
					sibling->getRight()->setBlack();
					rbptr.node->rotateLeft();
				}else if(sibling->getLeft()->isRed()){	// right-left, case 5
					sibling->rotateRight();
					sibling->setBlack();
					rbptr.node->rotateLeft();
				}else{	// sibling and its chilren are all black
					sibling->setRed();
					if(rbptr.node->_isBlack()){	// case 3
						isLeft = rbptr.node->isLeft();
						rbptr.node = rbptr.node->getParent();
						goUp = (rbptr.node != (RedBlackNode<T>*)0);
					}else rbptr.node->setBlack();	// case 4
				}
			}else{	// delete black right child
				sibling = rbptr.node->getLeft();
				if(sibling->_isRed()){
					rbptr.node->rotateRight();	// case 2
				}
				
				sibling = rbptr.node->getLeft();	// now it must be a black node
				if(sibling->getLeft()->isRed()){	// right-right, case 6
					sibling->getLeft()->setBlack();
					rbptr.node->rotateRight();
				}else if(sibling->getRight()->isRed()){	// left-right, case 5
					sibling->rotateLeft();
					sibling->setBlack();
					rbptr.node->rotateRight();
				}else{	// sibling and its chilren are all black
					sibling->setRed();
					if(rbptr.node->_isBlack()){	// case 3
						isLeft = rbptr.node->isLeft();
						rbptr.node = rbptr.node->getParent();
						goUp = (rbptr.node != (RedBlackNode<T>*)0);
					}else rbptr.node->setBlack();	// case 4
				}
			}
		}while(goUp);
	}
	
public:
	CALLCONV bool removeNode(RedBlackNode<T> *node){
		if(node == (RedBlackNode<T>*)0) return false;
		RedBlackNode<T> *temp0, *temp1 = node;
		if((temp0 = node->getRight()) != (RedBlackNode<T>*)0){
			// if node has a right child, find the first node
			// (leftmost node) in its right sub-tree
			// which is the smallest node that is not smaller than node
			do{
				temp1 = temp0;
				temp0 = temp0->getLeft();
			}while(temp0 != (RedBlackNode<T>*)0);
			swapKey(node, temp1);
			if((temp0 = temp1->getRight()) != (RedBlackNode<T>*)0){
				// The found node is not a leaf
				swapKey(temp1, temp0);
				temp1 = temp0;
			}
		}else if((temp0 = node->getLeft()) != (RedBlackNode<T>*)0){
			// node only has a left leaf
			temp1 = temp0;
			swapKey(node, temp1);
		}else{
			if(root == node){	// case 1: deleting root
				root = (RedBlackNode<T>*)0;
				return true;
			}
		}
		// now temp1 is the node to be removed
		temp0 = temp1->getParent();
		if(temp1->isLeft()) temp0->setLeftChild((RedBlackNode<T>*)0);
		else temp0->setRightChild((RedBlackNode<T>*)0);
		
		if(temp1->_isBlack()){
			typename RedBlackNode<T>::RedBlackPointer rbptr(temp0);
			rbptr.flag.value = temp1->left.flag.value;
			doubleBlack(rbptr);
			root = root->getRoot();
		}
	}
	
	CALLCONV bool _removeNode(RedBlackNode<T> *node){
		if(node == (RedBlackNode<T>*)0) return false;
		RedBlackNode<T> *temp0, *temp1 = node;
		if((temp0 = node->getRight()) != (RedBlackNode<T>*)0){
			// if node has a right child, find the first node
			// (leftmost node) in its right sub-tree
			// which is the smallest node that is not smaller than node
			do{
				temp1 = temp0;
				temp0 = temp0->getLeft();
			}while(temp0 != (RedBlackNode<T>*)0);
			swapNode(node, temp1);
			if((temp0 = node->getRight()) != (RedBlackNode<T>*)0){
				// The found node is not a leaf
				swapNode(node, temp0);
			}
		}else if((temp1 = node->getLeft()) != (RedBlackNode<T>*)0){
			// node only has a left leaf
			swapNode(node, temp1);
		}else{
			if(root == node){	// case 1: deleting root
				root = (RedBlackNode<T>*)0;
				return true;
			}
		}
		temp0 = node->getParent();
		if(node->isLeft()) temp0->setLeftChild((RedBlackNode<T>*)0);
		else temp0->setRightChild((RedBlackNode<T>*)0);
		
		if(node->_isBlack()){
			typename RedBlackNode<T>::RedBlackPointer rbptr(temp0);
			rbptr.flag.value = node->left.flag.value;
			doubleBlack(rbptr);
		}
		root = root->getRoot();
	}
}; // class RedBlackTree<T>

#endif	// _RED_BLACK_TREE_H_
